【Leetcode题解】151-Reverse Words in a String

文章目录

1. 1. 题目
2. 2. 思路
3. 3. 代码
4. 4. 改进

本系列代码见我的Leetcode仓库

题目

Given an input string, reverse the string word by word.
For example,
Given s = “the sky is blue”,
return “blue is sky the”.

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

看例子就很清楚了，用人话描述就是正话反说，每个单词逆序输出就行了。

思路

首先正常情况下的解法很容易想到，两种思路：

• 整句全部逆置，再逐个单词逆置
• 按单词分别逆置

我采取了第二种思路，从句子最后一个字符开始向左读，先逐个读入字符，此时是逆序的，当遇到空格时候说明前一个单词结束了，将这个单词翻转（成为正的顺序），进入结果队列。读完后结果队列就是最终结果。
这个题目很简单，只需要注意几种异常的判例：

• 空(“”)
• 空格或单字符(“ “,”a”)
• 单个词(“word”,”at”)
• 多余空格输入(“ a pig”,”a fool”,”a joke “)

把这些都处理掉，就可以Accept了

代码

Language:java

public class Solution {
    public String reverseWords(String s) {
    if(s.length()<=1)
        return s.equals(" ")?"":s;//处理单个字符或空输入
        StringBuffer tr = new StringBuffer();
        StringBuffer re = new StringBuffer();
        for(int i=s.length()-1;i>=0;i--){
            if(s.charAt(i)!=' '){
                tr.append(s.charAt(i));
                if(i>0 && s.charAt(i-1) == ' '){
                    re.append(tr.reverse());
                    re.append(' ');
                    tr.setLength(0);
                }
                else if(i<=0){
                    re.append(tr.reverse());
                }
            }
        }
        if(re.length()>1 && re.charAt(re.length()-1) == ' ')
            re.deleteCharAt(re.length()-1);//处理多余空格
        return re.toString();
    }
}

改进

时空复杂度均为O(n)
判例上还属于穷举的方式，应该有改进空间。